package com.frx.sort.heap;

import java.util.Arrays;

/**
 * Created with IDEA
 *
 * @author: xrf
 * @Date: 2019/11/13
 * @Time: 14:32
 */
public class TestOne {
    public static void main(String[] args){
        int[] arr = {3,1,2,4,5,7,6};
        heapSort(arr);
    }
    public static void heapSort(int[] arr){
        heapify(arr);
        System.out.println(Arrays.toString(arr));
        for (int n=arr.length-1;n>=1;n--){
            int temp = arr[n];
            arr[n] = arr[0];
            arr[0] = temp;
            siftdown(arr,0,n);
        }
        System.out.println(Arrays.toString(arr));
    }

    private static void heapify(int[] arr){
        int index = arr.length-1;
        for (int n= (index-1)/2;n>=0;n--){
            siftdown(arr,n,arr.length);
        }
    }
    private static void siftdown(int[] arr,int n,int k){
        while (true){
            int maxIndex = n;
            if (2*n+1<k && arr[2*n+1] > arr[n]){
                maxIndex = 2*n+1;
            }
            if (2*n+2<k && arr[2*n+2] > arr[maxIndex]){
                maxIndex = 2*n+2;
            }
            if (n==maxIndex){
                break;
            }
            int temp = arr[maxIndex];
            arr[maxIndex] = arr[n];
            arr[n] = temp;
            n = maxIndex;
        }
    }

}
